﻿#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY 1000000
#define MAX_VERTEX_NUM 20

//定义弧的权值信息
typedef struct Arccell
{
    int adj; //权值
} Arccell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //图的邻接矩阵
//定义结点信息
typedef struct VertexInfo
{
    char name[20];//结点[村庄]名称
} VertexInfo;
//图的结构
typedef struct Mgraph
{
    VertexInfo vexs[MAX_VERTEX_NUM];//顶点数组
    AdjMatrix arcs;//邻接矩阵
    int vernum, arcnum;//分别指定顶点数和边数
} Mgraph;


//对图的初始化
Mgraph initgraph(int a,int b)
{
    Mgraph c;
    c.vernum = a;
    c.arcnum = b;
   //村庄名字赋值
    strcpy(c.vexs[0].name,"a");
    strcpy(c.vexs[1].name,"b");
    strcpy(c.vexs[2].name,"c");
    strcpy(c.vexs[3].name,"d");

    //依次设置各弧的信息
    for (int i = 0; i < c.vernum; i++)
    {
        //先初始化邻接矩阵,相同点设置为0，其他全部设置为INFINITY（无穷大）
        for (int j = 0; j < c.vernum; j++)
        {
            c.arcs[i][j].adj = INFINITY;
            if (i == j)
            {
                c.arcs[i][j].adj = 0;
            }
        }
    }
    //需要设置的权值
    c.arcs[0][1].adj=7;
    c.arcs[0][3].adj=5;
    c.arcs[1][2].adj=4;
    c.arcs[2][0].adj=6;
    c.arcs[2][1].adj=6;
    c.arcs[3][0].adj=8;
    c.arcs[3][2].adj=6;
    return c;
}

//输出邻接矩阵
void printMatrix(Mgraph c)
{
    printf("该图的邻接矩阵如下所示：\n");
    int count = 0;//用于计数
    for (int i = 0; i < c.vernum; i++)
        for (int j = 0; j < c.vernum; j++)
        {
            if (c.arcs[i][j].adj == INFINITY)
                printf("   #");
            else
                printf("%4d", c.arcs[i][j].adj);
            count++;
            if (count % c.vernum == 0)
                printf("\n");
        }
}

void ShortestPath_Floyd(Mgraph G, int dis[][MAX_VERTEX_NUM])
{
    //用floyd算法求有向网G中各对定点v和w之间的最短路径及其带权长度dis[v][w]
    for (int v = 0; v < G.vernum; v++)
        for (int w = 0; w < G.vernum; w++)
        {
            //对各结点之间初始化已知距离
            dis[v][w] = G.arcs[v][w].adj;
        }

    for (int u = 0; u < G.vernum; u++)
        for (int v = 0; v < G.vernum; v++)
            for (int w = 0; w < G.vernum; w++)
            {
                if (dis[v][u] + dis[u][w] < dis[v][w])
                {
                    //从v经u到w的路径更短
                    dis[v][w] = dis[v][u] + dis[u][w];
                }
            }

}
//输出距离矩阵
void printDis(Mgraph G, int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
{
    printf("\n经过Flyod算法之后各顶点之间的距离如下：\n");
    for (int i = 0; i < G.vernum; i++)
    {
        for (int j = 0; j < G.vernum; j++)
        {
            if (dis[i][j] >= 1000000)
                printf("   #");
            else
                printf("%4d", dis[i][j]);

        }
        printf("\n");
    }
}

//得到偏心度degree[]数组
void getDegree(Mgraph G, int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM], int degree[])
{
    for (int i = 0; i < G.vernum; i++)
    {
        int max = dis[0][i];
        for (int j = 0; j < G.vernum; j++)
        {
            if (dis[j][i] > max)
                max = dis[j][i];
        }
        degree[i] = max;
    }
}



int main()
{
    Mgraph c = initgraph(4,7);
    //输出邻接矩阵
    printMatrix(c);

    
    //定义距离数组，调用Floyd算法得到结果
    int dis[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    ShortestPath_Floyd(c, dis);

    //输出各个顶点之间的距离矩阵
    printDis(c, dis);

    //存放每个顶点到其他顶点的最短距离的最大值
    int degree[4];
    getDegree(c, dis, degree);
   
    printf("\n每个顶点到其他顶点的最短距离的最大值。 ：\n");
    for (int i = 0; i < c.vernum; i++)
    {
        if (degree[i] >= 1000000)
            printf("   #\n");
        else
            printf("%4d\n", degree[i]);
    }

    //得到最小村庄的编号和名称
    int num;
    int min = degree[0];
    for (int i = 0; i < c.vernum; i++)
    {
        if (min > degree[i])
            min = degree[i];
    }

    for (int i = 0; i < c.vernum; i++)
    {
        if (min == degree[i])
        {
            num = i;
            break;
        }
    }
    printf("医院应该建立在村庄:   %4s \n", c.vexs[num].name);
    return 0;
    
}